Project 3: Grover's Algorithm for Database Search

Description

Grover's algorithm is a quantum algorithm that provides a quadratic speedup for searching an unstructured database compared to classical algorithms. While a classical search requires, on average, N/2 queries to a database of size N, Grover's algorithm requires only about sqrt(N) queries.

Objectives

• Understand the concept of an "oracle" in quantum computing.
• Implement the Grover diffusion operator (amplitude amplification).
• Create a quantum circuit that uses Grover's algorithm to find a specific item in an unstructured list.

Implementation Details

1. Framework: Use a quantum computing framework like Qiskit or Cirq.
2. The Algorithm:
   • Initialization: Start with a uniform superposition of all possible states.
   • Oracle: Create a quantum "oracle" that recognizes the marked item and flips its phase.
   • Diffusion Operator: Apply the Grover diffusion operator, which amplifies the amplitude of the marked item and reduces the amplitude of the other items.
   • Iteration: Repeat the oracle and diffusion steps about sqrt(N) times.
   • Measurement: Measure the qubits. The result will be the marked item with a high probability.
3. Code Example (Qiskit for a 2-qubit search):

from qiskit import QuantumCircuit, execute, Aer
from qiskit.visualization import plot_histogram

# The item to find (e.g., '11')
marked_item = '11'

# Create a quantum circuit
circuit = QuantumCircuit(2, 2)

# Initial superposition
circuit.h([0, 1])

# Oracle for '11'
circuit.cz(0, 1)

# Diffusion operator
circuit.h([0, 1])
circuit.z([0, 1])
circuit.cz(0, 1)
circuit.h([0, 1])

# Measurement
circuit.measure([0, 1], [0, 1])

# Execute the circuit
backend = Aer.get_backend('qasm_simulator')
job = execute(circuit, backend, shots=1024)
result = job.result()
counts = result.get_counts(circuit)

# Plot the results
plot_histogram(counts)